package com.lw.leetcode.back.b;

/**
 * Created with IntelliJ IDEA.
 * back
 * 1306. 跳跃游戏 III
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/13 16:29
 */
public class CanReach {

    private int[] arr;
    private int[] flags;

    public boolean canReach(int[] arr, int start) {
        this.arr = arr;
        flags = new int[arr.length];
        return find(start);
    }

    private boolean find(int start) {
        if (start < 0 || start >= arr.length) {
            return false;
        }
        if (arr[start] == 0) {
            return true;
        }
        if (flags[start] == 0) {
            flags[start] = 1;
            boolean b = find(start - arr[start]);
            if (b) {
                return true;
            }
        }
        if (flags[start] == 1) {
            flags[start] = 2;
            boolean b = find(start + arr[start]);
            if (b) {
                return true;
            }
        }
        flags[start] = 3;
        return false;
    }

}
